Hash tables are a fundamental building block in diverse applications such as databases, search engines, statistics processing, and dynamic script languages. Hash tables are a family of containers that associate keys with values. Hash tables calculate placement position for an item stored in an entry of the table, i.e., a bucket, using its hash value and a current capacity of the container. However containers usually need to dynamically increase capacity, which means either reallocation or allocation of an additional chunk of memory. So, increased capacity leads to invalidation of item placement and requires items to be moved to new places, which is commonly referred to as rehashing.
For known concurrent algorithms for hash tables, when a thread decides to resize a container, it blocks (i.e., temporarily stops) some (or even all) concurrent operations on the table until it finishes both resizing and rehashing processes. This leads to degradation in concurrency, and thus in performance. Another problem is that running time and complexity of operations with resizing differ significantly from the same operations without resizing.